Discrete Mathematics

Resources

Textbook online site
Katex Math Syntax
Snip Math

This will cover the following topics

• elementary logic
• set theory and functions
• equivalence relations
• partial orders
• mathematical induction
  combinatorics(including permutations, combinations, selections, and - distributions)
• binomial theorem
• formal power series and generating functions
• partial fractions and the solution of elementary recurrence relations

Module 1: Logic and Proofs

Logic is the basis of all mathematical reasoning, and of all automated reasoning. It has practical applications to the design of computing machines, to the specification of systems, to artificial intelligence, to computer programming, to programming languages, and to other areas of computer science, as well as to many other fields of study.
Learning Objectives

By the end of this module, you should be able to:

• Define, identify and write propositions
• Apply negations and logical connectives to build compound propositions
  Create conditional statements and derive their converse, contrapositive and - inverse statements
• Use truth tables to determine the truth values of compound propositions
• Define the terms tautology, contradiction, logically equivalent
• Use truth tables to establish the logical equivalence of compound - propositions
• Use the rules of logical equivalences to establish the logical equivalence - of compound proposition
• Define satisfiability and determine the satisfiability of compound - propositions
• Be able to identify the various rules of inference
• Understand the various methods of proof and how to use them

Required Readings

Rosen, Kenneth H., Discrete Mathematics and its Applications, 8th Edition ISBN: 978-1-259-67651-2

Chapter 1

Module 2: Sets, Functions and Rates of Growth

Many important discrete structures are built using sets, which are collections of objects. Among the discrete structures built from sets are combinations, unordered collections of objects used extensively in counting; relations, sets of ordered pairs that represent relationships between objects, and finite state machines, used to model computing machines. Functions also play important roles throughout discrete mathematics. They are used to represent the computational complexity of algorithms, to study the size of sets, to count objects, and in a myriad of other ways.

By the end of this module, you should be able to:

• Define and describe sets
• Use Set notation and Venn diagrams
• Identify and describe important sets
• Define and calculate Cartesian products of sets
  Perform Union, Intersection, Complementation, and Difference operations on sets
• Prove set identities using logical equivalencies
• Identify the types of functions and their rates of growth

References

Rosen, Kenneth H., Discrete Mathematics and its Applications, 8th Edition ISBN: 978-1-259-67651-2

Chapters 2 (2.1 -2.3) and 3 ( 3.2)

Module 3: Number Theory

The part of mathematics devoted to the study of the set of integers and their properties is known as number theory. In this module we will develop some of the important concepts of number theory including many of those used in computer science.
Learning Objectives

By the end of this module, you should be able to:

• Define and apply integer division
• Define and apply the Division ‘Algorithm’
  Apply modular arithmetic to determine the quotient, remainder and establish congruences
• Construct integer representations for:
  • Base Expansions
  • Binary Expansions
  • Octal Expansions
  • Hexadecimal Expansions
• Study and apply base conversion algorithms
• Study and apply algorithms for integer operations
• Define prime numbers
• Understand and apply the Fundamental Theorem of Arithmetic
• Define Greatest Common Divisors (gcd) and Least Common Multiples (lcm)
  Understand and apply the Euclidian Algorithm to find the gcd of two integers
• Define and solve linear congruences
  Explain and apply the Chinese Remainder Theorem to solve linear congruences
• Apply Fermat’s Little Theorem

References

Rosen, Kenneth H., Discrete Mathematics and its Applications, 8th Edition ISBN: 978-1-259-67651-2

Chapters 4.1 - 4.4

Module 4: Sequences and Series, Mathematical Induction, Basic Combinatorics and Probability

This module introduces the notion of a sequence, which represents ordered lists of elements. We will introduce some important types of sequences, and we will show how to define the terms of a sequence using earlier terms. We will also introduce the notation used to express summations, which represent the addition of terms from a sequence. The relative sizes of infinite sets can be studied by introducing the notion of the size, or cardinality, of a set: we say that a set is countable when it is finite or has the same size as the set of positive integers. We will study the concept of mathematical induction and apply proofs using induction.

Suppose that a password on a computer system consists of six, seven, or eight characters. Each of these characters must be a digit or a letter of the alphabet. Each password must contain at least one digit. How many such passwords are there? The techniques needed to answer this question and a wide variety of other counting problems will be introduced in this section. We will also solve linear recurrence relations and consider the basics of discrete probability.

By the end of this module, you should be able to:

• Define and analyze sequences.
• Find the value of sums and double sums
• Determine whether sets are finite, countably infinite or uncountable
• Understand and explain mathematical induction
• Solve counting problems using
  • Basic counting principles
  • Sum, Product and Subtraction rules
  • Explain the Pigeonhole Principle
• Apply the Pigeonhole Principle to solve counting problems
• Explain the Generalized Pigeonhole Principle
• Apply the Generalized Pigeonhole Principle to solve counting problems
• Apply the Binomial Theorem to find coefficients of binomial expansions
• Solve homogeneous second order linear recurrence relations with constant coefficients
• Understand the rules of basic discrete probability and solve applied problems

References

Rosen, Kenneth H., Discrete Mathematics and its Applications, 8th Edition ISBN: 978-1-259-67651-2

Chapters 2 (2.4, 2.5) and 5.1, 5.2, 6.1 - 6.5, 7.1, 7.2, 8.1, 8.2